package com.gxc.array;

import java.util.TreeMap;

/**
 * 3102. 最小化曼哈顿距离
 * 给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。
 *
 * 两点之间的距离定义为它们的
 * 曼哈顿距离
 *
 * 请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。
 *
 * 示例 1：
 *
 * 输入：points = [[3,10],[5,15],[10,2],[4,4]]
 * 输出：12
 * 解释：移除每个点后的最大距离如下所示：
 * - 移除第 0 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间，为 |5 - 10| + |15 - 2| = 18 。
 * - 移除第 1 个点后，最大距离在点 (3, 10) 和 (10, 2) 之间，为 |3 - 10| + |10 - 2| = 15 。
 * - 移除第 2 个点后，最大距离在点 (5, 15) 和 (4, 4) 之间，为 |5 - 4| + |15 - 4| = 12 。
 * - 移除第 3 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间的，为 |5 - 10| + |15 - 2| = 18 。
 * 在恰好移除一个点后，任意两点之间的最大距离可能的最小值是 12 。
 * 示例 2：
 *
 * 输入：points = [[1,1],[1,1],[1,1]]
 * 输出：0
 * 解释：移除任一点后，任意两点之间的最大距离都是 0 。
 */
public class MinimumDistance {

    public static void main(String[] args) {
        //System.out.println(handle(new int[][]{{3,10},{5,15},{10,2},{4,4}}));

        System.out.println(handle(new int[][]{{9,10},{9,4},{8,9}}));
    }

    /**
     * 曼哈顿距离与切比雪夫距离的相互转化
     * 曼哈顿距离转切比雪夫距离
     * (x, y) = max(|(x1 + y1) - (x2 + y2)|,|(x1-y1) - (x2-y2)|)
     *
     * 切比雪夫距离转曼哈顿距离
     * (x,y)  = ((x+y)/2, (x-y)/2)
     * @param points
     * @return
     */
    public static int handle(int[][] points) {
        TreeMap<Integer, Integer> tA = new TreeMap<>();
        TreeMap<Integer, Integer> tS = new TreeMap<>();
        int res = Integer.MAX_VALUE;
        //曼哈顿 坐标转为  x+y  ,x-y
        //两个点的坐标 = max(|(x1 + y1) - (x2 + y2)|,|(x1-y1) - (x2-y2)|)
        for (int i = 0; i < points.length; i++) {
            tA.put(points[i][0] + points[i][1], tA.getOrDefault(points[i][0]+ points[i][1], 0)+1);
            tS.put(points[i][0] - points[i][1], tS.getOrDefault(points[i][0] - points[i][1],0)+1);
        }
        for (int i = 0; i < points.length; i++) {
            //每次移除当前坐标
            int i1 = points[i][0] + points[i][1];
            int i2 = points[i][0] - points[i][1];
            tA.put(i1, tA.get(i1)-1);
            tS.put(i2, tS.get(i2)-1);
            if (tA.get(i1) == 0) {
                tA.remove(i1);
            }
            if (tS.get(i2) == 0) {
                tS.remove(i2);
            }

            //计算坐标移除后的最大距离的最小值
            res = Math.min(res, Math.max(Math.abs(tS.lastKey() - tS.firstKey()), Math.abs(tA.lastKey() - tA.firstKey())));

            //加回当前坐标
            tA.put(i1, tA.getOrDefault(i1, 0)+1);
            tS.put(i2, tS.getOrDefault(i2,0)+1);
        }
        return res;
    }
}
